package net.guruqu.cds;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;
import java.util.Vector;
import java.util.concurrent.ConcurrentHashMap;

import com.sun.org.apache.bcel.internal.generic.GETSTATIC;

public class ColorNode extends Node {

	int round;
	HashMap<IntPair, Vector<Integer>> coverEquivalent;
	HashMap<Integer, Boolean> surviveList;
	boolean chosen;
	boolean converge;
	float chosenProbability;
	static Random random;

	static {
		random = new Random(137);
	}

	public ColorNode() {
		round = 0;
		chosen = false;
		nodeCover = new HashMap<Integer, LinkedList<IntPair>>();
		coverEquivalent = new HashMap<IntPair, Vector<Integer>>();
		surviveList = new HashMap<Integer, Boolean>();
		chosenProbability = 0.5f;
		chosen=true;
	}

	private static Collection<Integer> findCommon(Collection<Integer> la,
			Collection<Integer> lb) {
		HashSet<Integer> sa = new HashSet<Integer>();
		HashSet<Integer> sb = new HashSet<Integer>();

		sa.addAll(la);
		sb.addAll(lb);

		HashSet<Integer> common = new HashSet<Integer>();
		for (Integer i : sa) {
			if (sb.contains(i))
				common.add(i);
		}
		return common;
	}

	private void announceChosenDecision() {
		HashSet<Integer> toSet = new HashSet<Integer>();
		for (IntPair i : coverEquivalent.keySet()) {
			toSet.addAll(coverEquivalent.get(i));
		}
		for (Integer i : toSet) {
			sendMessage(i, isChosen());
		}
	}

	public boolean colourFinished = false;
	int finishRound = -1;
	int currentColorDecision = -1;
	int finishCount = 0;
	int maxDegree = -1;
	HashMap<Integer, LinkedList<IntPair>> nodeCover;

	HashSet<Integer> notSelected;

	@Override
	public void executeNode() {
		HashMap<Integer, LinkedList<Object>> incoming = getIncomingMessage();
		if (round == 0) {
			setText("RET N");
			// Round 0 , every node send its neighbour information to all its
			// neighbour
			Vector<Integer> neighbour = getNeighbour();
			for (Integer i : neighbour) {
				sendMessage(i, neighbour);
			}
			for (int i = 0; i < neighbour.size(); i++) {
				// surviveList.put(neighbour.get(i), Boolean.FALSE);
				for (int j = i + 1; j < neighbour.size(); j++) {
					coverEquivalent.put(new IntPair(neighbour.get(i), neighbour
							.get(j)), new Vector<Integer>());

				}
			}
		}

		if (round == 1) {
			setText("CONF G");
			// Get 2 hop neighbour cover equivalent , Build the conflict graph
			// based on that
			LinkedList<Object> removeList = new LinkedList<Object>();
			for (IntPair i : coverEquivalent.keySet()) {
				Collection<Integer> na = (Collection) incoming.get(i.value[0])
						.getFirst();
				Collection<Integer> nb = (Collection) incoming.get(i.value[1])
						.getFirst();

				Collection<Integer> common = findCommon(na, nb);
				common.remove((Object) getUID());
				if (nb.contains(i.value[0]) && na.contains(i.value[1]))
					removeList.add(i);
				else {
					for (Integer j : common) {
						LinkedList<IntPair> pair = null;
						if (!nodeCover.keySet().contains(j)) {
							pair = new LinkedList<IntPair>();
							nodeCover.put(j, pair);
						} else
							pair = nodeCover.get(j);
						pair.add(i);
					}
				}
				coverEquivalent.get(i).addAll(common);

				// System.out.print(getUID() + "=");
				// System.out.println(common);
			}
			for (Object rm : removeList) {
				coverEquivalent.remove(rm);
			}

			notSelected = new HashSet<Integer>();
			clearIncomingMessage();
//			floodMessage((Integer) nodeCover.size());
			if(nodeCover.size()>getNetwork().maxDeg)
				getNetwork().maxDeg=nodeCover.size();
		}
		if (round == 2) {
			setText("FND MX DEG");
			// Find the max degree
//			for (Integer i : incoming.keySet()) {
//				int deg = ((Integer) incoming.get(i).removeFirst());
//				if (deg > maxDegree)
//					maxDegree = deg;
//			}
			maxDegree = getNetwork().maxDeg;
			clearIncomingMessage();
			availableColors = new Vector<Integer>();
			for (int i = 0; i <= maxDegree; i++) {
				availableColors.add(i);
			}
			currentColorDecision = random.nextInt(maxDegree+1);
			for (Integer twoHop : nodeCover.keySet()) {
				sendMessage(twoHop,
						new Object[] { currentColorDecision, false });
			}
		}
		if (round > 2 && !colourFinished) {
			// Randomized Colouring
			setText("CL: " + currentColorDecision);
			boolean unique = true;
			boolean smallest = true;
			for (Integer twoHop : nodeCover.keySet()) {
				if (incoming.get(twoHop) == null)
					continue;
				Object inc[] = (Object[]) incoming.get(twoHop).removeLast();
				Integer decision = (Integer) inc[0];
				boolean decided = (Boolean) inc[1];

				if (decision != -1 && decided) {
					availableColors.remove(decision);
				}
				if (decision == currentColorDecision)
					unique = false;
				if (twoHop < getUID() && !decided)
					smallest = false;

			}
			clearIncomingMessage();
			if (unique || smallest) {
				colourFinished = true;
			} else {
				currentColorDecision = availableColors.get(random
						.nextInt(availableColors.size()));
			}
			for (Integer twoHop : nodeCover.keySet()) {
				sendMessage(twoHop, new Object[] { currentColorDecision,
						colourFinished });
			}
		}

		if (colourFinished && !getNetwork().globalColourFinished) {
			// If color for this node is fixed, don't send out any message any
			// more.
			clearIncomingMessage();
		}
		if (getNetwork().globalColourFinished) {
			// Execute find minimal set cover
			if (finishRound == -1) {
				finishRound = round;
				// setText("C<" + currentColorDecision + "> "
				// + (colourFinished ? "D" : "U"));
			}

			for (Integer i : incoming.keySet()) {
				LinkedList msg = incoming.get(i);
				if (!nodeCover.keySet().contains(i))
					throw new RuntimeException(
							"UnExpected Message From Non-2-hop-neighbour: " + i);
				notSelected.add(i);
			}
			clearIncomingMessage();
			if (round - finishRound == currentColorDecision) {
				// It is time to execute the node base on the color
				// setText("CDS<" + round + ">" + currentColorDecision);

				boolean globalSafe = true;
				for (IntPair pair : coverEquivalent.keySet()) {
					Vector<Integer> equivalent = coverEquivalent.get(pair);
					boolean safe = false;
					for (Integer i : equivalent) {
						if (!notSelected.contains(i)) {
							safe = true;
							break;
						}
					}
					if (!safe) {
						globalSafe = false;
						break;
					}
				}
				if (globalSafe) {
					// Need to select this node in.
					setChosen(false);
					setText("");
					for (Integer i : nodeCover.keySet()) {
						sendMessage(i, new Object());
					}
				} else {
					setText("X");
				}
				converge = true;
			}
		}

		round++;
	}

	Vector<Integer> availableColors;

	public static class IntPair {
		public Integer value[];

		public IntPair(int a, int b) {
			value = new Integer[] { a, b };
		}

		public String toString() {
			return "{" + value[0] + "," + value[1] + "}";
		}

		public int hashCode() {
			return value[0].hashCode() * value[1].hashCode();
		}

		public boolean equals(Object obj) {
			return ((IntPair) obj).value[0] == value[0]
					&& ((IntPair) obj).value[1] == value[1];
		}
	}

	public static void main(String s[]) {
		// HashMap<IntPair,Object> o = new HashMap<IntPair, Object>();
		// o.put(new IntPair(1,2), new Object());
		// System.out.println(o.get(new IntPair(1,2)));
	}

	public boolean isChosen() {
		return chosen;
	}

	public void setChosen(boolean chosen) {
		this.chosen = chosen;
	}

	public boolean isConverge() {
		return converge;
	}

	public void setConverge(boolean converge) {
		this.converge = converge;
	}
}
